'''
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

 

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''


class Solution:
    def strStr(self, s: str, t: str) -> int:

        '''KMP模板'''

        def prefix_function(s):
            n = len(s)
            pi = [0] * n

            j = 0
            for i in range(1, n):
                while j > 0 and s[i] != s[j]:  # 当前位置s[i]与s[j]不等
                    j = pi[j - 1]  # j指向之前位置，s[i]与s[j]继续比较

                if s[i] == s[j]:  # s[i]与s[j]相等，j+1，指向后一位
                    j += 1

                pi[i] = j
            return pi

        '''主程序'''
        n, m = len(s), len(t)
        pi = prefix_function(t)  # 预处理得到t的前缀函数

        '''再次基于KMP的思想在s中匹配t'''
        j = 0
        for i in range(n):

            while j > 0 and s[i] != t[j]:
                j = pi[j - 1]

            if s[i] == t[j]:
                j += 1
                if j == m:  # 匹配到了t，直接返回
                    return i - m + 1
        return -1
